#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
using namespace std;

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        int ans = 0;
        for (int i = n - 1; i >= 0; --i)
        {
            for (int j = i; j < n; ++j)
            {
                if (s[i] == s[j])
                {
                    if (i == j || i + 1 == j)
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i + 1][j - 1];
                }
                if (dp[i][j] == true) ++ans;
            }
        }
        return ans;
    }

    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        int start = 0, len = 0;
        for (int i = n - 1; i >= 0; --i)
        {
            for (int j = i; j < n; ++j)
            {
                if (s[i] == s[j])
                {
                    if (i == j || i + 1 == j)
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i + 1][j - 1];
                }
                if (dp[i][j] == true && j - i + 1 > len)
                {
                    start = i;
                    len = j - i + 1;
                }
            }
        }
        return s.substr(start, len);
    }

    string longestPalindrome(string s) {
        int n = s.size();
        int begin = 0, len = 0;
        for (int i = 0; i < n; ++i)
        {
            int left = i - 1, right = i + 1;
            while (left >= 0 && right < n && s[left] == s[right])
            {
                --left, ++right;
            }
            if (right - left - 1 > len)
            {
                len = right - left - 1;
                begin = left + 1;
            }
            left = i, right = i + 1;
            while (left >= 0 && right < n && s[left] == s[right])
            {
                --left, ++right;
            }
            if (right - left - 1 > len)
            {
                len = right - left - 1;
                begin = left + 1;
            }
        }
        return s.substr(begin, len);
    }

    string addBinary(string a, string b) {
        int cur1 = a.size() - 1, cur2 = b.size() - 1, carry = 0;
        string ans;
        while (cur1 >= 0 || cur2 >= 0 || carry)
        {
            if (cur1 >= 0)
                carry += a[cur1--] - '0';
            if (cur2 >= 0)
                carry += b[cur2--] - '0';
            ans += carry % 2 + '0';
            carry /= 2;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }

    string multiply(string num1, string num2) {
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        int m = num1.size(), n = num2.size();
        vector<int> mul(m + n);
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                mul[i + j] += (num1[i] - '0') * (num2[j] - '0');
        int carry = 0;
        string ans;
        for (int num : mul)
        {
            carry += num;
            ans += carry % 10 + '0';
            carry /= 10;
        }
        while (carry)
        {
            ans += carry % 10 + '0';
            carry /= 10;
        }

        while (ans.size() > 1 && ans.back() == '0') ans.pop_back();
        reverse(ans.begin(), ans.end());
        return ans;
    }

    string removeDuplicates(string s) {
        string ans;
        for (int i = 0; i < s.size(); ++i)
        {
            if (!ans.empty() && s[i] == ans.back())
                ans.pop_back();
            else
                ans.push_back(s[i]);
        }
        return ans;
    }

    string changestr(string str)
    {
        string ss;
        for (int i = 0; i < str.size(); ++i)
        {
            if (!ss.empty() && str[i] == '#') ss.pop_back();
            else if (str[i] != '#') ss.push_back(str[i]);
        }
        return ss;
    }

    bool backspaceCompare(string s, string t) {
        return changestr(s) == changestr(t);
    }

    int calculate(string s) {
        vector<int> st;
        char flag = '+';
        int i = 0, n = s.size();
        while (i < n)
        {
            if (s[i] == ' ') ++i;
            else if (s[i] >= '0' && s[i] <= '9')
            {
                int num = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9')
                    num = num * 10 + (s[i++] - '0');
                if (flag == '+')
                    st.push_back(num);
                else if (flag == '-')
                    st.push_back(-num);
                else if (flag == '*')
                    st.back() *= num;
                else
                    st.back() /= num;
            }
            else
            {
                flag = s[i];
                ++i;
            }
        }
        int ans = 0;
        for (auto x : st)
        {
            ans += x;
        }
        return ans;
    }

    string decodeString(string s) {
        stack<string> str;
        stack<int> num;
        str.push("");
        int i = 0, n = s.size();
        while (i < n)
        {
            if (s[i] <= '9' && s[i] >= '0')
            {
                int tn = 0;
                while (s[i] <= '9' && s[i] >= '0')
                {
                    tn = tn * 10 + (s[i] - '0');
                    ++i;
                }
                num.push(tn);
            }
            else if (s[i] == '[')
            {
                ++i;
                string t;
                while (s[i] >= 'a' && s[i] <= 'z')
                {
                    t += s[i];
                    ++i;
                }
                str.push(t);
            }
            else if (s[i] == ']')
            {
                int x = num.top();
                num.pop();
                string t = str.top();
                str.pop();
                while (x--)
                {
                    str.top() += t;
                }
                ++i;
            }
            else {
                string t;
                while (i < n && s[i] >= 'a' && s[i] <= 'z')
                {
                    t += s[i];
                    ++i;
                }
                str.top() += t;
            }
        }
        return str.top();
    }

    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int j = 0;
        stack<int> st;
        for (int i = 0; i < pushed.size(); ++i)
        {
            st.push(pushed[i]);
            while (st.size() && j < popped.size() && popped[j] == st.top())
            {
                st.pop();
                ++j;
            }
            if (st.empty() && j == popped.size()) return true;
        }
        return false;
    }

    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode() : val(0), left(nullptr), right(nullptr) {}
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
        TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
        
    };

    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> Q;
        int levelSize = 0;
        if (root)
        {
            Q.push(root);
            levelSize = 1;
        }
        vector<vector<int>> ans;
        while (levelSize > 0)
        {
            vector<int> level;
            while (levelSize--)
            {
                TreeNode* front = Q.front();
                Q.pop();
                level.push_back(front->val);
                if (front->left) Q.push(front->left);
                if (front->right) Q.push(front->right);
            }
            ans.push_back(level);
            levelSize = Q.size();
        }
        return ans;
    }
}; 